﻿//定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，
//所以 base 看起来是这样的：
//"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
//给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
//
//
//输入：s = "a"
//输出：1
//解释：字符串 s 的子字符串 "a" 在 base 中出现。
//
//输入：s = "cac"
//输出：2
//解释：字符串 s 有两个子字符串("a", "c") 在 base 中出现。
//
//输入：s = "zab"
//输出：6
//解释：字符串 s 有六个子字符串("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
//
//提示：
//	1 <= s.length <= 10^5
//	s 由小写英文字母组成


class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.size();
        // 1. 利⽤ dp 求出每个位置结尾的最⻓连续⼦数组的⻓度
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++)
            if (s[i] - 1 == s[i - 1] || (s[i - 1] == 'z' && s[i] == 'a'))
                dp[i] = dp[i - 1] + 1;

        // 2. 计算每⼀个字符结尾的最⻓连续⼦数组的⻓度
        int hash[26] = { 0 };
        for (int i = 0; i < n; i++)
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        // 3. 将结果累加起来
        int sum = 0;
        for (auto x : hash)
            sum += x;

        return sum;
    }
};
